{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Inorder Successor in BST II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inorderSuccessor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的中序后继 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉搜索树和其中的一个节点 <code>node</code> ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 <code>null</code> 。</p>\n",
    "\n",
    "<p>一个节点 <code>node</code> 的中序后继是键值比 <code>node.val</code> 大所有的节点中键值最小的那个。</p>\n",
    "\n",
    "<p>你可以直接访问结点，但无法直接访问树。每个节点都会有其父节点的引用。节点 <code>Node</code> 定义如下：</p>\n",
    "\n",
    "<pre>\n",
    "class Node {\n",
    "    public int val;\n",
    "    public Node left;\n",
    "    public Node right;\n",
    "    public Node parent;\n",
    "}</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_1.PNG\" style=\"height: 117px; width: 122px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [2,1,3], node = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解析：</strong>1 的中序后继结点是 2 。注意节点和返回值都是 Node 类型的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_2.PNG\" style=\"height: 229px; width: 246px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [5,3,6,2,4,null,null,1], node = 6\n",
    "<strong>输出：</strong>null\n",
    "<strong>解析：</strong>该结点没有中序后继，因此返回<code> null 。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/02/02/285_example_34.PNG\" style=\"height: 335px; width: 438px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15\n",
    "<strong>输出：</strong>17\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/02/02/285_example_34.PNG\" style=\"height: 335px; width: 438px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13\n",
    "<strong>输出：</strong>15\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [0], node = 0\n",
    "<strong>输出：</strong>null\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内。</li>\n",
    "\t<li><code>-10<sup>5</sup> <= Node.val <= 10<sup>5</sup></code></li>\n",
    "\t<li>树中各结点的值均保证唯一。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能否在不访问任何结点的值的情况下解决问题?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [inorder-successor-in-bst-ii](https://leetcode.cn/problems/inorder-successor-in-bst-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [inorder-successor-in-bst-ii](https://leetcode.cn/problems/inorder-successor-in-bst-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]\\n1', '[5,3,6,2,4,null,null,1]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "            \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.right:\n",
    "            res = node.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "            return res\n",
    "        if node.parent and node.parent.left == node:\n",
    "            return node.parent\n",
    "        if node.parent:\n",
    "            res = node.parent\n",
    "            while res.parent and res.parent.right == res:\n",
    "                res = res.parent\n",
    "            if res:\n",
    "                return res.parent\n",
    "            else:\n",
    "                return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        \n",
    "        if not node.right:\n",
    "            par = node.parent\n",
    "            while par:\n",
    "                if par.val > node.val:\n",
    "                    return par\n",
    "                else:\n",
    "                    par = par.parent\n",
    "            else: return None\n",
    "        \n",
    "        elif not node.right.left:\n",
    "            return node.right\n",
    "        else:\n",
    "            successor = node.right.left\n",
    "            while successor.left:\n",
    "                successor = successor.left\n",
    "            return successor\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.right:\n",
    "            res = node.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        while node.parent and node.parent.right == node:\n",
    "            node = node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "\n",
    "        if node.parent is None:\n",
    "            return None\n",
    "        # 有parent，且node.right is None\n",
    "        if node.parent.left == node:\n",
    "            return node.parent\n",
    "        \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Node':\n",
    "        # 找右子樹第一個\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        \n",
    "        # 找Parent們中，第一個成為左子樹的，找到後Return Parent\n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            node=node.right\n",
    "            while node.left:\n",
    "                node=node.left\n",
    "            return node\n",
    "        \n",
    "        while node.parent and node.parent.right==node:\n",
    "            node=node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node==None:\n",
    "            return None \n",
    "        if node.right != None:\n",
    "            node = node.right\n",
    "            while node.left !=None:\n",
    "                node= node.left \n",
    "            return node \n",
    "        \n",
    "        while node.parent !=None and node.parent.right == node:\n",
    "            node = node.parent\n",
    "        \n",
    "        return node.parent\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            while node.parent and node.parent.left != node:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            node=node.right\n",
    "            while node.left:\n",
    "                node=node.left\n",
    "            return node\n",
    "        while node.parent and node==node.parent.right:\n",
    "            node=node.parent\n",
    "        return node.parent\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node is None:\n",
    "            return None\n",
    "\n",
    "        if node.right is None:\n",
    "            cur_child = node\n",
    "            iter_p = node.parent\n",
    "            while iter_p is not None and iter_p.right == cur_child:\n",
    "                next_p = iter_p.parent\n",
    "                cur_child = iter_p\n",
    "                iter_p = next_p\n",
    "\n",
    "            if iter_p is None:\n",
    "                return None\n",
    "            return iter_p\n",
    "\n",
    "        right_child = node.right\n",
    "        iter_node = right_child\n",
    "        while iter_node.left is not None:\n",
    "            iter_node = iter_node.left\n",
    "        return iter_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        \n",
    "        # node -> [node+1, ]\n",
    "        # inorder 左 中 右\n",
    "        # 对于当前节点，\n",
    "        # 如果有右子节点 则取值范围应为 [node+1, ] 最小的，即从右子节点从左一撸到底\n",
    "        # 如果他没有右子节点，则要从parent找，找处在 [node+1, parent]最小的\n",
    "\n",
    "        # def dfs(root, upperBound):\n",
    "        #     # 搜索以root为根的子树 [node+1, upperBound] 范围内最小的值\n",
    "\n",
    "        #     if root.val <= node.val:\n",
    "        #         return dfs(root.parent, )\n",
    "        dumbNode = Node(inf)\n",
    "        x = node.val\n",
    "        def dfs(root):\n",
    "            nonlocal x\n",
    "            if root is None:\n",
    "                return None\n",
    "            \n",
    "            if root.val <= x:\n",
    "                return dfs(root.right)\n",
    "            else:\n",
    "                tmp = dfs(root.left)\n",
    "                return tmp if tmp is not None else root \n",
    "\n",
    "\n",
    "        if node.right is not None:\n",
    "            cur = node.right\n",
    "            while cur.left is not None:\n",
    "                cur = cur.left\n",
    "            return cur\n",
    "        else:\n",
    "            cur = node.parent\n",
    "            while cur is not None and cur.val < x:\n",
    "                cur = cur.parent\n",
    "            \n",
    "            # 找cur子树中大于 node 的最小节点\n",
    "            return dfs(cur)\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        # return dfs(node, inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            t = node.val\n",
    "            while node.parent:\n",
    "                node = node.parent\n",
    "                if node.val > t:\n",
    "                    return node\n",
    "            return None\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        p = node.right\n",
    "        while p and p.left:\n",
    "            p = p.left\n",
    "\n",
    "        if p is not None:\n",
    "            return p\n",
    "\n",
    "        p = node\n",
    "        while p.parent and p.parent.right == p:\n",
    "            p = p.parent\n",
    "        \n",
    "        return p.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 1.当前节点如果有右子树，找右子树的最小节点（最左）\n",
    "        # 2.当前节点没有右子树，向上找第一个大于当前节点的父节点\n",
    "        if node.right:\n",
    "            node = node.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        else:\n",
    "            while node.parent and node.parent.right == node:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "\n",
    "\n",
    "        if not node.right:\n",
    "            while node.parent and node == node.parent.right:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "        right = node.right\n",
    "        while right.left:\n",
    "            right = right.left\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for a Node.\r\n",
    "class Node:\r\n",
    "    def __init__(self, val):\r\n",
    "        self.val = val\r\n",
    "        self.left = None\r\n",
    "        self.right = None\r\n",
    "        self.parent = None\r\n",
    "\"\"\"\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Node':\r\n",
    "        if node.right:          #有右子 则是右子树的最左下\r\n",
    "            node = node.right\r\n",
    "            while node.left:\r\n",
    "                node = node.left\r\n",
    "            return node\r\n",
    "        else:\r\n",
    "            while node.parent and node.parent.right == node:\r\n",
    "                node = node.parent\r\n",
    "            return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right!=None:\n",
    "            node=node.right\n",
    "            while node.left!=None:\n",
    "                node=node.left\n",
    "            return node\n",
    "        else:\n",
    "            pnode=node.parent\n",
    "            if pnode!=None and pnode.right==node:\n",
    "                while pnode!=None and pnode.right==node:\n",
    "                    node=pnode\n",
    "                    pnode=pnode.parent\n",
    "\n",
    "                return pnode\n",
    "            else:\n",
    "                return pnode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        p = node.right\n",
    "        while p and p.left:\n",
    "            p = p.left\n",
    "        if p:\n",
    "            return p\n",
    "        p = node\n",
    "        while p.parent and p.parent.right == p:\n",
    "            p = p.parent\n",
    "        return p.parent\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # has right ,then right min val\n",
    "        # node is parent left child,then parent\n",
    "        # node is parent right child,then keep finding until node is left child ,return parent \n",
    "\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root \n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root\n",
    "        else:\n",
    "            while node.parent and node.parent.right == node:\n",
    "                node = node.parent\n",
    "            return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        succ = None\n",
    "        if node.right:\n",
    "            succ = node.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "\n",
    "        # if node.parent is None:\n",
    "        #     return None\n",
    "        # 有parent，且node.right is None\n",
    "        # if node.parent.left == node:\n",
    "        #     return node.parent\n",
    "        \n",
    "        pos = node\n",
    "        while pos.parent:\n",
    "            if pos==pos.parent.left:\n",
    "                succ = pos.parent\n",
    "                break\n",
    "            pos = pos.parent\n",
    "        return succ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        root = node\n",
    "        while root.parent:  root = root.parent\n",
    "        \n",
    "        stack = [None, root]\n",
    "        visited = {}\n",
    "        while True:\n",
    "            cur = stack.pop()\n",
    "            if isinstance(cur, Node):\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur.val)\n",
    "                if cur.left:    stack.append(cur.left)\n",
    "                visited[cur.val] = cur\n",
    "            elif cur == node.val:\n",
    "                if isinstance(stack[-1], int):  cur = visited[stack[-1]]\n",
    "                else:   cur = stack[-1]\n",
    "                if not cur or cur.val in visited: return cur\n",
    "                while cur.left: cur = cur.left\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "\n",
    "        # 中序后继 后继的东西\n",
    "        if node.right:\n",
    "            cur = node.right\n",
    "            while cur.left:\n",
    "                cur = cur.left\n",
    "            return cur\n",
    "        else:\n",
    "\n",
    "            while node.parent and node.parent.val < node.val:\n",
    "                node = node.parent\n",
    "            return node.parent\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        # 第一种情况，在右下子节点\n",
    "        if node.right:\n",
    "            root = node.right\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "            return root\n",
    "        \n",
    "        # 第二种情况，在上方父节点\n",
    "        while node.parent and node == node.parent.right:\n",
    "            node = node.parent\n",
    "        return node.parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':\n",
    "        z = node\n",
    "        root = node\n",
    "        while node: \n",
    "            root = node\n",
    "            node = node.parent\n",
    "        lst = []\n",
    "        def f(o):\n",
    "            if not o: return\n",
    "            f(o.left)\n",
    "            lst.append(o)\n",
    "            f(o.right)\n",
    "        f(root)\n",
    "        for x, y in pairwise(lst):\n",
    "            if x == z: return y\n",
    "        return None"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
